/**
 * @Author: JiuQi 玖柒
 * @Date: 2021/7/8 20:59
 * @Description: 反转字符串中的单词
 * 先将字符串变为字符数组，然后定义两个指针，start 和 end，start 指向字符数组的起始位置，end 开始也让它也指向字符数组起始位置，遍历 end ，
 * 一直到 end == ' ' ，也就是当 end 指向空格的时候，执行反转函数，反转 start 和 end-1 这两个指针所指向的单词（正好指向单词的一头一尾，
 * end 指向空格，end-1 就指向前一单词的结尾，end+1 就指向下一单词的开头），然后让 start 和 end 同时指向下一个单词的开头，开始下一个单词的反转。
 * <p>
 * 我们知道，只有当 end 指向空格的时候，才会执行反转函数，反转前面那个单词，但循环到最后一个单词发现后面没有空格，肿么办？？
 * <p>
 * 嘿嘿，我们只需在最开始传入的字符串后面加一个空格，最后返回的时候去掉这个空格不就好了嘛！
 */
public class T557 {
    public static void main(String[] args) {
        String s = "Let's take LeetCode contest";
        System.out.println(new Solution577().reverseWords(s));
    }
}

class Solution577 {
    public String reverseWords(String s) {
        int k = 0, n = s.length() - 1;
        // 在原字符串的最后面加一个空格，方便我们处理最后一个单词
        s = s.concat(" ");
        // 将字符串变为字符数组
        char[] array = s.toCharArray();
        int start = 0, end = 0;
        while (end < array.length) {
            while (array[end] != ' ') {
                end++;
            }
            reverse(array, start, end - 1);
            start = end + 1;
            end = start;
            k++;
        }
        String res = new String(array);
        // 用substring()函数去掉我们之前加在字符串上的最后一个空格
        return res.substring(0, array.length - 1);
    }

    // 反转函数
    void reverse(char[] ch, int left, int right) {
        while (left < right) {
            char temp = ch[left];
            ch[left] = ch[right];
            ch[right] = temp;
            left++;
            right--;
        }
    }
}
